from tools_algorithm import *


class Solution:
    def minCost(self, nums: List[int], cost: List[int]) -> int:
        n = len(nums)
        ids = list(range(n))
        ids.sort(key=lambda a: nums[a])
        nums.sort()
        ct = [cost[i] for i in ids]
        # print(nums)
        # print(ct)
        psm = list(accumulate(ct, initial=0))
        # print(psm)
        c, sm = 0, sum([i * j for i, j in zip(nums, ct)])
        ans = sm
        for num in range(nums[0], nums[-1] + 1):
            i = bisect_left(nums, num)
            p, q = psm[i], psm[-1] - psm[i]
            sm = sm + (p - q) * (num - c)
            c = num
            ans = min(ans, sm)

        return ans


class Solution:
    def minCost(self, nums: List[int], cost: List[int]) -> int:
        n = len(nums)
        ids = sorted(range(n), key=lambda a: nums[a])
        nums.sort()
        ct = [cost[i] for i in ids]
        psm = list(accumulate(ct, initial=0))
        c, sm = 0, sum([i * j for i, j in zip(nums, ct)])
        ans = sm
        for num in nums:
            i = bisect_left(nums, num)
            p, q = psm[i], psm[-1] - psm[i]
            sm += (p - q) * (num - c)
            ans = min(ans, sm)
            c = num

        return ans


s = Solution()
print(s.minCost(nums=[1, 3, 5, 2], cost=[2, 3, 1, 14]))

# a = [1, 1, 1, 3, 3, 3, 5, 5, 5]
# print(bisect_left(a, 2), bisect_right(a, 2))


fl = test_file_path(__file__, 2)
c = []
n = 100000
for _ in range(n):
    c.append(random.randint(1, 10000))
print(c, file=fl)
c = []
for _ in range(n):
    c.append(random.randint(1, 100))
print(c, file=fl)
